package com.zhaofan.recursion;

import org.junit.After;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class Interview0806 {
    public static Map<Integer, Integer> storage = new HashMap<>();

    public static void main(String[] args) {
        int a = f(5);
        System.out.println(a);
    }

    static int f(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (storage.containsKey(n)) {
            return storage.get(n);
        }
        int i = f(n - 1) + f(n - 2);
        storage.put(n, i);
        return i;
    }

    static int i = 0;

    @Test
    public void test1() {
        ArrayList<Integer> a = new ArrayList<>();
        ArrayList<Integer> b = new ArrayList<>();
        ArrayList<Integer> c = new ArrayList<>();
        a.add(2);
        a.add(1);
        a.add(0);
        hanota(a, b, c);
        System.out.println(c);
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    public void move(int size, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (size == 1) {
            c.add(a.remove(a.size() - 1));
            System.out.println("退出条件只剩下一个盘子了,将最大的盘子从a移动到c,a=" + a.toString() + ",b=" + b.toString() + ",c=" + c.toString());
            return;
        }
        /**
         * 为什么b,c位置互换?可以理解为,当move(a,b,c)时,我们想把圆盘从a放到c时,b当作辅助柱,但当我们想将a(n-1)个盘放到b时,那么c就是辅助柱
         */
        move(size - 1, a, c, b);
//        System.out.println("把"+(size-1)+"个盘子从a-b挪动,a="+a.toString()+",b="+b.toString()+",c="+c.toString());
        Integer remove = a.remove(a.size() - 1);
        c.add(remove);
        System.out.println("只剩下一个盘子了,将最大的盘子从a移动到c,a=" + a.toString() + ",b=" + b.toString() + ",c=" + c.toString());
        move(size - 1, b, a, c);
//        System.out.println("把"+(size-1)+"个盘子从b-c挪动,a="+a.toString()+",b="+b.toString()+",c="+c.toString());
    }
}
